package leetCode;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Set;

public class PlantingWithNoAdjacent {
    public int[] gardenNoAdj(int N, int[][] paths) {
        HashMap<Integer, Set<Integer>> map = new HashMap<>();
        for (int[] path :
                paths) {
            int x = path[0];
            int y = path[1];
            addToMap(map, x, y);
            addToMap(map, y, x);
        }
        int[] res = new int[N];
        for (int i = 0; i < N; i++) {
            res[i] = findcolor(map, i, res);
        }
        return res;
    }

    private int findcolor(HashMap<Integer, Set<Integer>> map, int i, int[] res) {
        boolean[] color = new boolean[5];
        if (!map.containsKey(i)) {
            return 1;
        }
        for (int y :
                map.get(i)) {
            if (res[y] != 0) {
                color[res[y]] = true;
            }
        }
        //鎵惧嚭鍙互鐢ㄧ殑棰滆壊
        for (int j = 1; j < 5; j++) {
            if (!color[j]) {
                return j;
            }
        }
        return 0;
    }

    private void addToMap(HashMap<Integer, Set<Integer>> map, int x, int y) {
        x--;
        y--;
        if (!map.containsKey(x)) {
            map.put(x, new HashSet<>());
        }
        map.get(x).add(y);
    }

    public static void main(String[] args) {
        int N = 3;
        int[][] paths = {{1, 2}, {2, 3}, {3, 1}};
        int[] res = new PlantingWithNoAdjacent().gardenNoAdj(N, paths);
        for (int i :
                res) {
            System.out.print(i);
        }
    }
}
